package com.zdp.leetcodeMiddle;


import java.util.ArrayList;
import java.util.List;

/*
* 题目描述：
* 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
提示：
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals 根据 intervals[i][0] 按 升序 排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105
* */
public class 插入区间_57 {
    public static void main(String[] args) {
        插入区间_57 demo = new 插入区间_57();
        int[][] intervals = new int[][] {
                {1,2},{3,5},{6,7},{8,10},{12,16}
        };
        int[] newInterval = new int[] {4,8};
        int[][] insert = demo.insert(intervals, newInterval);
        for(int[] i : insert){
            for(int l : i){
                System.out.print(l+",");
            }
            System.out.println();
        }
    }

    /*
    * 解题思路： 给我们的 是 无重叠的 区间列表 且按 inttervals[i][0] 升序排列
    *  将区间分为两个 一个为 要插入的区间， 一个为当前遍历到的区间
    *  只有当 要插入的区间 与 当前区间 没有产生交集时，才会发生插入操作
    *  当 要插入区间和 当前区间 产生交集时， 更新要插入的区间（计算交集）
    *   根据题意 ， 只会产生一个 重叠区间，其余区间都是不重叠的，所以对于 要插入区间，
    * 其实只要插入一次即可。
    *
    * */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length == 0){
            return new int[][]{
                    newInterval
            };
        }
       List<int[]> result = new ArrayList<>();
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        // 只会产生一个重叠区间
        boolean flag = true;
       for(int[] interval : intervals){
           // 判断当前要插入的区间 与 当前区间的 交集
           if(interval[1] < newStart){
               // 直接插入即可
               //当前区间 在 要插入区间的 左侧 且无交集
               // 列表按升序 左侧的先插入
               result.add(interval);
           }else if(interval[0] > newEnd){
               // 当前区间 在 要插入区间的 右侧
               // 所以要先插入 插入区间 再插入 当前区间
               //  要先插入 要插入的区间 ，再插入当前区间
               if(flag){
                   result.add(new int[] {newStart,newEnd});
                    flag = false;
               }
               result.add(interval);
           }else{
               // 说明有交集，得到交集 这个交集暂时不插入到result 中
               // 用于比较 当当前遍历到区间 于 要插入的交集 无交集，且>要插入的交集时，
               // 才将这个交集插入
               newStart = Math.min(interval[0],newStart);
               newEnd = Math.max(interval[1],newEnd);
           }
       }
       if(flag){
           // 表示 要插入的区间是在列表的最后 ---> 要插入的区间还未插入
           result.add(new int[] {newStart,newEnd});
       }
        return result.toArray(new int[result.size()][]);
    }
}
